第四课 STL查找

发表于 | 更新于 | 分类于

教学内容

STL的三种查找算法；

STL其他常用函数；

教学目标

学生熟练的掌握STL的三种查找算法。

重难点

STL三种查找算法之间的不同和联系。

课前准备

巩固知识点，复习习题

引入课题

查找一组数据中满足小于b大于a的数字的个数，分析题目：
暴力算法，时间复杂度$o(M*N)$

1
2
3
4
5
6
7
8
for(int i=1; i <= M; i++)
{
    scanf("&d&d",&a,&b);
    int cnt=0;
    for(int j=1; j <= N; j++)
        if(( x[j] >= a && x[j] <= b) cnt++;
    cout << cnt << endl;
}

该程序的时间复杂度为$o(M*N)$，其中其中M的极限为50000，N的极限为1000000。
所以在最坏情况下，要运算:$50000*1000000 = 500$亿次.现在的计算机，
在1秒之内运算次数大概为5千万次左右，所以暴力方法肯定不能通过本题的全部数据！！！
所以，我们要学习新的算法，来高效的完成任务！！！

讲授新课

STL查找函数

STL 中常用的用于查找的函数有三个：lower_bound、upper_bound、binary_search，一般 lower_bound 最为常用。

lower_bound 用于在一个升序序列中查找某个元素，并返回第一个不小于该元素的元素的下标，如果找不到，则返回指向序列中最后一个元素之后的迭代器。

upper_bound 用于在一个升序序列中查找某个元素，并返回第一个大于该元素的元素的迭代器，如果找不到，则返回指向序列中最后一个元素之后的迭代器。

binary_search 用于确定某个元素有没有在一个升序序列中出现过，返回 true 或 false。

三个函数的时间复杂度均为$O({\log}n)$。

测试代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
int a[8] = { -9, 5, -1, 2, 7, 1, -2, 2 }, n = 8;

sort(a, a + n);

// a = { -9, -2, -1, 1, 2, 2, 5, 7 }

int *p1 = lower_bound(a, a + n, 1);
// p1 指向 a 中第 4 个元素 a[3] = 1

int *p2 = lower_bound(a, a + n, 2);
// p2 指向 a 中第 5 个元素 a[4] = 2

int *p3 = upper_bound(a, a + n, 2);
// p3 指向 a 中第 7 个元素 a[6] = 5

int *p4 = lower_bound(a, a + n, 8);
// p4 = a + n，因为数组 a 中没有不小于 8 的元素，此时访问 *p4 会越界

bool flag = binary_search(a, a + n, 3);
// flag = false 因为数组 a 中没有 3

ps: (得到查找函数返回的值需要减去数组的首地址，代码如下)

1
2
3
4
5
int p = lower_bound(a, a + n, 8) - a;  
//数组a有使用下标为0的元素

int p = lower_bound(a + 1, a + 1 + n, 8) - a;
// 数组a没有使用下标为0的元素

STL交换函数

使用 swap函数交换两个变量的值。

1
2
3
int a = -1, b = 1;
swap(a, b);
// a = 1, b = -1

STL较大、较小值

使用max 和 min 来取得两个数中较大或较小的。

int a = -1, b = 890;
x = max(a, b);   // 结果为 890
y = min(a, b);   // 结果为-1

课堂小结

课后反思

是否关照到每位同学
多关心学生家庭作业完成情况